package com.berchen.数据结构.二叉树.顺序二叉树;

/**
 * 顺序二叉树
 * 顺序二叉树 必须是一个完全二叉树
 * 用数组存储  同时还能前序后序中序遍历
 * 树的节点以0 开始编号
 * 当前节点的左子节点索引为 2*n+1
 * 当前节点的右子节点索引为 2*n+2
 * 当前节点的父节点的索引为 (n-1)/2
 *                  0
 *             1         2
 *          3     4   5     6
 *
 *
 *  应用场景：堆排序
 *
 */
public class ArrBinaryTree {

    public static void main(String[] args){

        // 这里就是一个顺序二叉树
        int arr[] ={1,2,3,4,5,6,7};
        preOrder(arr,0);
        System.out.println();
    }

    /**
     * 前序遍历
     * @param arr
     * @param index
     */
    public static void preOrder(int[] arr,int index){
        if(index>=arr.length){
            return;
        }
        if(arr.length<=0){
            System.out.println("树中没有元素");
        }
        System.out.print(arr[index]+",");
        // 左递归
        preOrder(arr,2*index+1);
        // 右递归
        preOrder(arr,2*index+2);
    }

    /**
     * 中序遍历
     * @param arr
     * @param index
     */
    public static void innOrder(int[] arr,int index){
        if(index>=arr.length){
            return;
        }
        if(arr.length<=0){
            System.out.println("树中没有元素");
        }

        // 左递归
        innOrder(arr,2*index+1);
        System.out.print(arr[index]+",");
        // 右递归
        innOrder(arr,2*index+2);
    }

    /**
     * 后序遍历
     * @param arr
     * @param index
     */
    public static void sufOrder(int[] arr,int index){
        if(index>=arr.length){
            return;
        }
        if(arr.length<=0){
            System.out.println("树中没有元素");
        }

        // 左递归
        sufOrder(arr,2*index+1);

        // 右递归
        sufOrder(arr,2*index+2);
        System.out.print(arr[index]+",");
    }
}
